// 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

function firstMissingPositive(nums: number[]): number {
    // 原地哈希表算法
    // 将数组的哈希表整理成 索引：i ，数值：i+1的形式
    for (let i = 0; i < nums.length; i++) {
        // 这里注意当nums[i] !== nums[nums[i] - 1]会造成一次无效交换，可能导致死循环
        // 记得加上并条件
        while (nums[i] >= 1 && nums[i] < nums.length && nums[i] !== nums[nums[i] - 1]) {
            let temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    // 检查哪个位置的哈希表不符合题意
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }
    // 若哈希表都满足题意，则返回length+1
    return nums.length + 1;
};

// 这道题目要求时间复杂度为On且空间复杂度为O1
// 故要满足题意其实考察的是一个原地哈希表的算法
// 正常来说其实我们只需从最小的正整数 1 开始，依次判断 2、 3 、4 直到数组的长度 N 是否在数组中；
// 如果当前考虑的数不在这个数组中，我们就找到了这个缺失的最小正整数；
// 这里能使用原地哈希算法的关键在于要找的数一定在 [1, N + 1] 左闭右闭（这里 N 是数组的长度）这个区间里。
// 我们可以就把原始的数组当做哈希表来使用。
// 可以采取这样的思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，
// 按照这种思路整理一遍数组。
// 这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。
// 在这里要注意一个方面，就是当nums[i] !== nums[nums[i] - 1]会造成一次无效交换，可能导致死循环
// 而且在用数组构造哈希表的时候，内层是一个while循环，因为交换过来的数字可能也不满足哈希表的规则
// 第二遍我们再遍历一次数组（哈希表整理后），第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。
